﻿using System;
using System.Collections.Generic;
using System.Text;

namespace 平衡二叉树
{
    /// <summary>
    /// 平衡二叉树
    /// </summary>
    public class AVLTree
    {
        private AVLNode root;  //根结点
        private int count;
        public int Count { get => count; private set => count = value; }


        /// <summary>
        /// AVL数的插入方法
        /// </summary>
        /// <param name="data"></param>
        public void Insert(int data)
        { 
            //插入节点
            #region 
            if (root == null)  //根结点空  则将新节点插入到根节点
            {
                root = new AVLNode(data);
                root.bF = 0;
                return;
            }
            AVLNode parent = root;       //表示当前节点的父节点
            AVLNode curNode = root;      //表示当前节点
            while (curNode != null)
            {
                parent = curNode;        //保存下个结点的父节点
                if (data < parent.data)
                {
                    curNode = parent.lC;
                }
                else
                {
                    curNode = parent.rC;
                }
            }
            //找到空节点
            curNode = new AVLNode(data);    //给空节点赋值  为当前插入节点
            curNode.parent = parent;        //当前节点的父节点为保存好的父节点
            curNode.bF = 0;
            if (data < parent.data)         //当前节点内容比父节点内容小  在左
            {
                parent.lC = curNode;
            }
            else
            {
                parent.rC = curNode;
            }
            #endregion  

            //每插入一个节点便要计算平衡因子
            //平衡因子为左子树高度减去右子树高度
             AddSymmetry(curNode);

            count++;
        }
        public void RotateLL(AVLNode parent)
        {
            //                 G                                  G
            //                 |                                  |
            //                 P                                 Cur
            //               /   \                            /      \
            //             Cur    X1                         C        P 
            //            /   \            ======>         /   \    /   \ 
            //           C     X2                         X3   X4   X2   X1
            //         /   \
            //        X3   X4

            AVLNode grandParent = parent.parent;
            AVLNode curNode = parent.lC;
            if (grandParent != null)   //当前子树有父节点
            {
                if (grandParent.lC == parent)
                {
                    grandParent.lC = curNode;
                    curNode.parent = grandParent;
                    //grandParent.bF--;
                }
                else
                {
                    grandParent.rC = curNode;
                    curNode.parent = grandParent;
                    //grandParent.bF++;
                }
            }
            else  //若不存在 上一节点
            {
                curNode.parent = null;
                root = curNode;
            }
            parent.lC = curNode.rC;   //将Cur的右孩子改为P的左孩子
            if (parent.lC != null)
            {
                parent.lC.parent = parent;    //将P改为X2的parent
            }
            curNode.rC = parent;    //将P改为Cur的右孩子
            parent.parent = curNode;
            curNode.bF--;
            parent.bF-=2;

        }
        public void RotateLR(AVLNode parent)
        {
            //                 G                                  G
            //                 |                                  |
            //                 P                                 C
            //               /   \                            /      \
            //             Cur    X1                        Cur       P 
            //            /   \            ======>         /   \    /   \ 
            //           X2    C                          X2   X3   X4   X1
            //               /   \
            //              X3   X4

            AVLNode grandParend = parent.parent;
            AVLNode curNode = parent.lC;
            AVLNode c = curNode.rC;
            if (grandParend != null)  
            {
                if (grandParend.lC == parent)
                {
                    grandParend.lC = c;
                    c.parent = grandParend;
                    //grandParend.bF--;
                }
                else
                {
                    grandParend.rC = c;
                    c.parent = grandParend;
                    //grandParend.bF++;
                }
            }
            else
            {
                c.parent = null;
                root = c;
            }

            //将Cur的右孩子设置成c的左孩子
            curNode.rC = c.lC;
            if (curNode.rC != null)
            {
                curNode.rC.parent = curNode;
            }
            //将p的左孩子设置成c 的右孩子

            parent.lC = c.rC;
            if (parent.lC != null)
            {
                parent.lC.parent = parent;
            }

            //将c的左孩子改为Cur
            c.lC = curNode;
            curNode.parent = c;

            //将c的右孩子改为P
            c.rC = parent;
            parent.parent = c;

            parent.bF = 0;
            curNode.bF++;
            c.bF = curNode.bF;
        }
        public void RotateRR(AVLNode parent)
        {
            //                 G                                      G
            //                 |                                      |
            //                 P                                     Cur
            //               /   \                                /       \
            //             X1    Cur                              P        C
            //                  /   \            ======>        /   \     /   \ 
            //                 X2    C                         X1   X2   X3   X4
            //                      /   \
            //                     X3   X4
            AVLNode grandParent = parent.parent;
            AVLNode curNode = parent.rC;
            if (grandParent != null)
            {
                if (grandParent.lC == parent)
                {
                    grandParent.lC = curNode;
                    curNode.parent = grandParent;
                    //grandParent.bF--;
                }
                else
                {
                    grandParent.rC = curNode;
                    curNode.parent = grandParent;
                    //grandParent.bF++;
                }
            }
            else
            {
                curNode.parent = null;
                root = curNode;
            }
            parent.rC = curNode.lC;
            if (parent.rC != null)
            {
                parent.rC.parent = parent;
            }
            curNode.lC = parent;
            parent.parent = curNode;
            parent.bF+=2;
            curNode.bF++;
        }
        public void RotateRL(AVLNode parent)
        {
            //                 G                                      G
            //                 |                                      |
            //                 P                                      C
            //               /   \                                /       \
            //             X1    Cur                              P       Cur
            //                  /   \            ======>        /   \     /   \ 
            //                 C     X2                        X1   X3   X4   X2
            //               /   \
            //              X3   X4
            AVLNode grandParent = parent.parent;
            AVLNode curNode = parent.rC;
            AVLNode c = curNode.lC;
            if (grandParent != null)
            {
                if (grandParent.lC == parent )
                {
                    grandParent.lC = c;
                    c.parent = grandParent;
                    //grandParent.bF--;
                }
                else
                {
                    grandParent.rC = c;
                    c.parent = grandParent;
                    //grandParent.bF++;
                }
            }
            else
            {
                c.parent = null;
                root = c;
            }

            curNode.lC = c.rC;
            if (curNode.lC != null)
            {
                curNode.lC.parent = curNode;
            }

            parent.rC = c.lC;
            if (parent.rC != null)
            {
                parent.rC.parent = parent;
            }

            c.rC = curNode;
            curNode.parent = c;

            c.lC = parent;
            parent.parent = c;


            parent.bF = 0;
            curNode.bF--;
            c.bF = -curNode.bF;  /////////////////////////////////////////////

        }

        

        /// <summary>
        /// 前序遍历
        /// </summary>
        /// <returns></returns>
        public void InOrderFormer()
        {
            _InOrder1(root);
        }
        private void _InOrder1(AVLNode node)
        {
            if (node == null)
            {
                return;
            }
            Console.Write(node.data + " ");
            _InOrder1(node.lC);
            _InOrder1(node.rC);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public void InOrderMiddle()
        {
            _InOrder2(root);
        }
        private void _InOrder2(AVLNode node)
        {
            if (node == null)
            {
                return;
            }
            _InOrder2(node.lC);
            Console.Write(node.data + " ");
            _InOrder2(node.rC);
        }

        /// <summary>
        /// 后续遍历
        /// </summary>
        public void InOrderAfter()
        {
            _InOrder3(root);
        }
        private void _InOrder3(AVLNode node)
        {
            if (node == null)
            {
                return;
            }
            _InOrder3(node.lC);
            _InOrder3(node.rC);
            Console.Write(node.data + " ");
        }


        public bool Delete(int val)
        {
            AVLNode curNode = root;


            while (true)
            {
                if (curNode == null) return false;
                if (curNode.data == val)
                {
                    DeleteNode(curNode);
                    count--;
                    return true;
                }
                if(val < curNode.data)
                {
                    curNode = curNode.lC;
                }
                else
                {
                    curNode = curNode.rC;
                }
            }
        }

        private void DeleteNode(AVLNode node)
        {
            AVLNode parent = node.parent;
            if(node.rC == null && node.lC == null)
            {
                if (parent == null)
                {
                    root = null;
                }else if (parent.lC == node)
                {
                    parent.bF--;
                    parent.lC = null;
                }
                else if(parent.rC == null)
                {
                    parent.bF++;
                    parent.rC = null;
                }
                DelSymmetry(parent);
                return;
            }
            if (node.rC != null && node.lC == null)
            {
                if (parent.lC == node)
                {
                    parent.bF--;
                }
                else if (parent.rC == null)
                {
                    parent.bF++;
                }
                AVLNode rc = node.rC;
                node.data = rc.data;
                node.bF = rc.bF;
                node.rC = rc.rC;
                node.lC = rc.lC;

                rc.rC.parent = node;
                rc.lC.parent = node;

                DelSymmetry(parent);
                return;
            }

            if (node.rC == null && node.lC != null)
            {
                if (parent.lC == node)
                {
                    parent.bF--;
                }
                else if (parent.rC == null)
                {
                    parent.bF++;
                }
                AVLNode lc = node.lC;
                node.data = lc.data;
                node.bF = lc.bF;
                node.rC = lc.rC;
                node.lC = lc.lC;

                lc.rC.parent = node;
                lc.lC.parent = node;

                DelSymmetry(parent);

                return;
            }


            AVLNode temp = node.rC;
            while (true)
            {
                if (temp.lC != null)
                {
                    temp = temp.lC;
                }
                else
                {
                    break;
                }
            }
            node.data = temp.data;
            DeleteNode(temp);

        }

        private void DelSymmetry(AVLNode node)   //删除后平横
        {
            AVLNode parent = node;
            AVLNode curNode = node;
            while (parent != null)   //该节点下删除的
            {
                if (parent.lC == curNode)       //更改节点因子   左边少 因子减  右边少  因子加
                {
                    parent.bF--;
                }
                else
                {
                    parent.bF++;
                }

                //判断  删除后节点是否还平衡
                if (parent.bF == 0)
                {
                    break;
                }
                else if (parent.bF == -1 || parent.bF == 1) // 回溯  检测上一个是否平横
                {
                    curNode = parent;
                    parent = curNode.parent;
                }
                else
                {
                    if (parent.bF == 2)
                    {
                        if (curNode.bF == 1)
                        {
                            RotateLL(parent);
                        }
                        else
                        {
                            RotateLR(parent);
                        }
                    }
                    else
                    {
                        if (curNode.bF == 1)
                        {
                            RotateRL(parent);
                        }
                        else
                        {
                            RotateRR(parent);
                        }
                    }
                    break;
                }
            }
        }
        private void AddSymmetry(AVLNode node)
        {
            AVLNode curNode = node;
            AVLNode parent = curNode.parent;
            while (parent != null)     //在该节点下添加的节点 所以更改它的因子
            {
                if (parent.lC == curNode)
                {
                    parent.bF++;
                }
                else        //若新节点在parent的右结点上 ， 平衡因子-1
                {
                    parent.bF--;
                }
                //接下来根据平衡因子判断当前父节点是否平衡    

                if (parent.bF == 0)   //若parent的平衡因子为0，则表示当前平衡状态，不需要变更
                {
                    break;
                }
                else if (parent.bF == -1 || parent.bF == 1) //若parent的平衡因子为-1或1，则需要回溯，验证上一个节点是否平衡
                {
                    curNode = parent;
                    parent = curNode.parent;
                }
                else   //parent的平衡因子为2 或-2 ， 则需要重新平衡二叉树
                {
                    if (parent.bF == 2)  //若左子树高于右子树 
                    {
                        if (curNode.bF == 1)    //LL
                        {
                            RotateLL(parent);   //平衡操作
                        }
                        else           //LR
                        {
                            RotateLR(parent);   //平衡操作
                        }
                    }
                    else               //右边高于左边
                    {
                        if (curNode.bF == -1)  //RR
                        {
                            RotateRR(parent);
                        }
                        else      //RL
                        {
                            RotateRL(parent);
                        }
                    }
                    break;
                }
            }
        }
    }
}

